import java.util.Stack;

/**
 * @author 03010570
 * @date 2020/07/09
 * describe:    LeetCode : 面试题 10.03 、搜索旋转数组  https://leetcode-cn.com/problems/search-rotate-array-lcci/
 */
public class LeetCode_interview_10_03 {

    public static void main(String[] args) {
//        int[] ints = {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14};
//        System.out.println(search(ints, 5));
//        System.out.println(search(ints, 11));
        System.out.println(search(new int[]{1,1,1,1,1,2,1,1,1, 11},2));

    }

    public static int search2(int[] arr, int target) {
        int start = 0, end = arr.length - 1;
        while (start < end) {
            int middle = start + ((end - start) >> 1);
            if (arr[middle] <= arr[end]) {
                end = middle;
            } else if (arr[middle] >= arr[start]) {
                start = middle + 1;
            }
        }
        // 判断 target 是处在 左区间还是 右区间
        if (target >= arr[0]) {
            end = start - 1;
            start = 0;
        } else {
            end = arr.length - 1;
        }

        while (start <= end) {
            int middle = start + ((end - start) >> 1);
            if (arr[middle] > target) {
                end = middle - 1;
            } else if (arr[middle] < target) {
                start = middle + 1;
            } else {
                if (middle == 0 || arr[middle - 1] != target) return middle;
                else end--;
            }
        }
        return -1;
    }

    /**
     * 取巧的办法：
     * 先找到中间旋转的值，最小值 （找旋转数组的最小值的下标）
     * 在优先判断 目标值是否处于左边的区间范围内，再进行二分查找，第一个等于给定值的元素 （第一个等于给定值的元素）
     *
     * @param arr
     * @param target
     * @return
     */
    public static int search(int[] arr, int target) {
        int start = 0, end = arr.length - 1;
        while (start <= end) {
            int middle = start + ((end - start) >> 1);
            if (arr[middle] < arr[end]) {
                end = middle;
            } else if (arr[middle] > arr[end]) {
                start = middle + 1;
            } else {
                end--;
            }
        }
        // 判断 target 是处在 左区间还是 右区间
        if (target >= arr[0]) {
            end = start - 1;
            start = 0;
        } else {
            end = arr.length - 1;
        }

        while (start <= end) {
            int middle = start + ((end - start) >> 1);
            if (arr[middle] > target) {
                end = middle - 1;
            } else if (arr[middle] < target) {
                start = middle + 1;
            } else {
                if (middle == 0 || arr[middle - 1] != target) return middle;
                else end--;
            }
        }
        return -1;
    }

}
